#include "./../../Headers/mathematics/math_order.h"

namespace Mathematics {
	namespace SortSpace {
		
		void LSort( int *set, const ulint &set_size ){
			using namespace Define;
			int xMin = set[0], xMax = xMin, delta = 1;
			
			for( register ulint i = 0; i < set_size; ++i ){
				xMin = Min( xMin , set[i] );
				xMax = Max( xMax , set[i] );
			}
			
			ulint t_size = ( (xMax - xMin + 1) / delta );
			int *t_aux = NULL;
			t_aux = ( int* ) malloc( t_size * sizeof( int ) );
			if(t_aux == NULL){
				cout << "Error! Couldn't allocate memory." << endl;
				exit(-1);
			}
			for( register ulint i = 0; i < t_size; ++i )
				t_aux[i] = 0;
			
			for( register ulint i = 0; i < set_size; ++i )
				++( t_aux[ set[i] - xMin ] );
			
			ulint j = 0;
			for( register ulint i = 0; i < t_size; ){
				if( t_aux[i]-- <= 0 ) {
					++i; continue;
				}
				set[j++] = xMin + i*delta;
			}
			
			free( t_aux );
		};
		
		void LSort( deque<int> &set ){
			using namespace Define;
			int xMin = set[0], xMax = xMin, delta = 1;
			
			for( register ulint i = 0; i < set.size(); ++i ){
				xMin = Min( xMin , set[i] );
				xMax = Max( xMax , set[i] );
			}
			
			ulint t_size = ( (xMax - xMin + 1) / delta );
			int *t_aux = NULL;
			t_aux = ( int* ) malloc( t_size * sizeof( int ) );
			if(t_aux == NULL){
				cout << "Error! Couldn't allocate memory." << endl;
				exit(-1);
			}
			for( register ulint i = 0; i < t_size; ++i )
				t_aux[i] = 0;
			
			for( register ulint i = 0; i < set.size(); ++i )
				++( t_aux[ set[i] - xMin ] );
			
			ulint j = 0;
			for( register ulint i = 0; i < t_size; ){
				if( t_aux[i]-- <= 0 ) {
					++i; continue;
				}
				set[j++] = xMin + i*delta;
			}
			
			free( t_aux );
		};
		
		// comparison for qsort
		int compare( const void *a, const void *b ){
			return ( ((int)a) < ((int)b) ? -1 : ( ((int)a) == ((int)b) ? 0 : 1 ) );
		};
		
		void QSort( int *set, const ulint &set_size ){
			qsort( set, set_size, sizeof(int), compare );
		};
		
		void SortTest() {
			cout << endl << "---Test:Sort---" << endl;
			
			ulint t_size = 30;
			int *t_aux = NULL;
			t_aux = ( int* ) malloc( t_size * sizeof( int ) );
			if(t_aux == NULL){
				cout << "erro" << endl;
				exit(-1);
			}
			
			cout << endl << ">> Generating" << endl;
			
			for( ulint i = 0; i < t_size; ++i ){
				t_aux[i] = rand()%10;
				cout << t_aux[i] << " ";
			}
			cout << endl;
			
			cout << endl << ">> Start LSort" << endl;
			TimeMeasure::Start();
			LSort( t_aux, t_size );
			cout << "Time : " << (double) TimeMeasure::End() << pendl;
			
			for( ulint i = 0; i < t_size; ++i )
				cout << t_aux[i] << " ";
			cout << endl;
			
			free( t_aux );
			
			cout << endl << "---TestEnd---" << endl;
		};
		
	};
};
